package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] a = {2, 66, 1, 53, 8, 3, 24, 6, 8, 1};
        System.out.println(Arrays.toString(a));
        sort1(a);
        System.out.println(Arrays.toString(a));

        //Arrays.sort(new int[]{});//快速排序
        //Arrays.sort(new Object[]{});//归并排序
    }

    /*
        1. gap循环从 a.length/2 到 1，修改 gap /= 2
        2. i循环，从gap递增到末尾
        3. 取出i位置的值存到临时变量
        4. j从i位置开始，向前 -=gap，j的范围>=gap
        5. 如果j-gap位置的值大，将这个值复制到j位置
           否则，结束j循环
        6. j循环结束后，临时值放到j位置
     */
    private static void sort(int[] a) {
        for (int gap = a.length / 2; gap >= 1; gap /= 2) {
            // 插入排序
            for (int i = gap; i < a.length; i++) {
                int tmp = a[i];
                int j = i;
                for (; j >= gap && a[j - gap] > tmp; j -= gap) {
                    //可以把这个判断写到上面for循环条件中，那这里可以省略if-else
                    //if (a[j - gap] > tmp) {
                    a[j] = a[j - gap];
                    //} else {
                    //    break;
                    //}
                }
                a[j] = tmp;
            }

        }
    }


    /*
        1. gap循环从 a.length/2 到 1，修改 gap /= 2
        2. i循环，从gap递增到末尾
        3. 取出i位置的值存到临时变量
        4. j从i位置开始，向前 -=gap，j的范围>=gap
        5. 如果j-gap位置的值大，将这个值复制到j位置
           否则，结束j循环
        6. j循环结束后，临时值放到j位置
     */
    private static void sort1(int[] a) {
        for (int gap = a.length / 2; gap >= 1; gap /= 2) {
            // 插入排序
            for (int i = gap; i < a.length; i++) {
                int tmp = a[i];
                int j = i-gap;
                for (; j >= 0; j -= gap) {
                    if (a[j] > tmp) {
                        a[j+gap] = a[j];
                    } else {
                        break;
                    }
                }
                a[j+gap] = tmp;
            }

        }
    }

}
